package com.xcc.dataStructures.demo14_algapplication;

/**
 * 动态规划解决01背包问题
 *
 */
public class Demo03_DynamicProgrammingKnapsack {

    public static void main(String[] args) {
        int[] w = {1, 4, 3};
        int[] v = {1500, 3000, 2000};
        knapsackSingle(v, w, 4);
    }

    /**
     * 求解01背包问题
     *          0   1       2       3       4
     *          0	0	    0	    0	    0
     *  1500    0	1500	1500	1500	1500
     *  3000    0	1500	1500	1500	3000
     *  2000    0	1500	1500	2000	3500
     *
     * @param v 商品的价值
     * @param w 商品的重量(体积)
     * @param c 商品的最大容量
     */
    public static void knapsackDim(int[] v, int[] w, int c) {
        //初始化二维数组，行表示商品的体积w 列表示容量从0->c
        int size = w.length;
        int[][] dp = new int[size + 1][c + 1];
        for (int i = 1; i <= size; i++) {
            for (int j = 0; j <= c; j++) {
                //当前商品的体积 大于 容量j 时 直接取上一行的数据
                dp[i][j] = dp[i - 1][j];
                if (w[i-1] <= j) {
                    //①dp[i - 1][j - w[i - 1]]为上一行的当前可用体积-当前商品体积  得到减去当前商品重量之后的最大价值 + v[i-1]
                    //②dp[i][j]实则为上一行的数据  与①直接比较大小
                    dp[i][j] = Math.max(dp[i][j], v[i - 1] + dp[i - 1][j - w[i - 1]]);
                }
            }
        }
        show(dp);
    }

    /**
     * 背包问题优化  使用一维数组
     *
     * @param v 商品的价值
     * @param w 商品的重量(体积)
     * @param c 商品的最大容量
     */
    public static void knapsackSingle(int[] v, int[] w, int c) {
        int[] dp = new int[c + 1];
        //第一次初始化dp
        for (int i = 0; i < c + 1; i++) {
            dp[i] = w[0] > i ?  0 : v[0];
        }

        for (int i = 1; i < w.length; i++) {
            //防止前面数据被覆盖，从后往前进行遍历
            for (int j = c; j >=0; j--) {
                if (w[i] <= j) {
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
            }
        }
        show(dp);
    }

    /**
     * 遍历
     */
    private static void show(int[] dp) {
        for (int i : dp) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }
    /**
     * 遍历
     */
    private static void show(int[][] dp) {
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
}
